//零钱兑换
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.size(); j++) {
                if (i - coins[j] >= 0 && dp[i - coins[j]] != -1)
                    dp[i] = min(dp[i - coins[j]] + 1, dp[i]);
            }
            if (dp[i] == INT_MAX)
                dp[i] = -1;
        }
        return dp[amount];
    }
};

//字符串解码
class Solution {
public:
    string decodeString(string s) {
        vector<int> Istack;
        vector<string> Sstack;
        Sstack.push_back("");
        int n = s.size();
        for (int i = 0; i < n; i++) {
            if (s[i] >= 'a' && s[i] <= 'z') {
                Sstack.back() += s[i];
            } else if (s[i] == ']') {
                int t = Istack.back();
                string _s;
                while (t) {
                    _s += Sstack.back();
                    t--;
                }
                Istack.pop_back();
                Sstack.pop_back();
                Sstack.back() += _s;
            } else {
                int t = 0;
                while (s[i] != '[') {
                    t = t * 10 + (s[i] - '0');
                    i++;
                }
                Istack.push_back(t);
                Sstack.push_back("");
            }
        }
        return Sstack.back();
    }
};

//